1. Field of the Invention
The present invention generally relates to digital image processing. More specifically, the present invention relates to the detection, in a digital image, of any predetermined pattern.
2. Discussion of the Related Art
A known method of such a detection is described hereafter in relation with FIGS. 1A and 1B.
FIG. 1A schematically illustrates a pattern 1, the possible presence of which is desired to be determined in a digital image. FIG. 1B illustrates a digital image 2 in which pattern 1 of FIG. 1A is searched. It is assumed, in this example, that image 2 does include pattern 1 and that image 2 has dimensions greater than those of pattern 1.
To detect the presence of pattern 1 in image 2, a reference image or window 3 containing only pattern 1 is used. The detection is performed by scanning image 2 with a current window 4 of same dimensions as reference window 3 and by comparing the content of the two windows 3 and 4. Such a comparison consists of evaluating the correlation degree between reference window 3 and current window 4. For this purpose, the Euclidean distance pixel by pixel, which is cumulated on the current and reference windows, is used. More specifically, for each pixel of the current window, the square of a distance EDi,j defined by the following relation is calculated:ED2i,j=(Pi,j−Ri,j)2, where
Pi,j is the value of the level of grey of the current pixel of current window 4, and where Ri,j is the value of the level of grey of the pixel of the reference window of same coordinates i,j in reference window 3.
Then, the squares of distances EDi,j are added on vertical dimension M (i ranging from 1 to M) and on horizontal dimension N (j ranging between 1 and N) of the current window, to deduce therefrom the Euclidean distance ED from a window to the other. This amounts to applying the following formula:
  ED  =                              ∑                      i            =            1                    M                ⁢                              ∑                          j              =              1                        N                    ⁢                      ED                          i              ,              j                        2                                .  
To enable locating the same patterns of different sizes, sum ED may be normalized. The energy of the current and reference windows is then, for example, used. The “energy” of a current or reference window designates the sum of the squares of the levels of grey of all the pixels in the considered window.
To localize pattern 1, Euclidean distance ED is calculated for all possible positions of the current window in the image. Pattern 1 then is at the location corresponding to minimum distance ED.
A disadvantage of this method is the great number of calculations to be performed. Indeed, assuming that A is the number of lines of image 2, and B the number of columns of image 2, and assuming that M is the number of lines of reference window 3 and N its number of columns, the total number of calculations is equal to the total number of pixels of reference image 3, that is, product MN, by the number of possible spatial positions for current window 4, that is, M*N*(A−M)*(B−N).
Another disadvantage of this method is its high sensitivity to luminosity conditions upon acquisition of the processed image or of the reference window. Indeed, as previously discussed, the correlation search is based on a difference of levels of grey. A variation in the acquisition conditions of images to be processed may locally modify the results by causing wrong detections or wrong rejections.